package jzoffer;

import leetcode.tree.TreeNode;

import java.util.Stack;

/**
 * B是不是A的子结构
 * @author MaoLin Wang
 * @date 2020/10/8 10:13 上午
 */
public class _26树的子结构 {
    public static boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A==null || B==null){
            return false;
        }
        Stack<TreeNode>stack=new Stack<>();
        stack.push(A);
        while (!stack.isEmpty()){
            TreeNode root = stack.pop();
            if (root.val==B.val && compare(root,B)){
                return true;
            }
            if (root.right!=null){
                stack.push(root.right);
            }
            if (root.left!=null){
                stack.push(root.left);
            }
        }
        return false;
    }

    private static boolean compare(TreeNode root, TreeNode child) {
        if (root==null && child==null){
            return true;
        }
        if (root==null){
            return false;
        }
        if (child==null){
            return true;
        }
        return root.val==child.val && compare(root.left,child.left) && compare(root.right,child.right);

    }

    public static void main(String[] args) {
        TreeNode root=new TreeNode(10);
        root.left=new TreeNode(12);
        root.right=new TreeNode(6);
        root.left.left=new TreeNode(8);
        root.left.right=new TreeNode(3);
        root.left.left.left=new TreeNode(11);

        TreeNode child=new TreeNode(10);
        child.left=new TreeNode(12);
        child.right=new TreeNode(6);
        child.left.left=new TreeNode(8);
        boolean subStructure = isSubStructure(root, child);
        System.out.println(subStructure);
    }
}
